This invention relates to the field of artificial intelligence, for example to the field of expert systems or knowledge-based systems.
Artificial intelligence (AI) technology is a discipline with an ultimate goal of providing a machine that is capable of reasoning, making inferences and following rules in a manner believed to model the human mind. A great deal of theoretical work has been done in this discipline, and much remains to be done. Artificial intelligence theory is beginning to find applications because of the hope that its principles can be effectively applied to develop better computer software and to provide to relatively untrained users sophisticated computer power to solve practical problems such as to assist in the analysis of massive amounts of relatively unprocessed data to aid in decision-making processes.
As AI technology begins to demonstrate potential and practical uses, tools are needed to speed development of practical computational systems. AI specialists have developed a number of AI-dedicated computer languages to assist in this development. Among the languages are LISP and PROLOG. However, these languages are not particularly easy for either skilled AI researchers or minimally-trained user/programmers to use to develop sophisticated and complex knowledge bases necessary to solve the problems related to artificial intelligence applications. Hence, tools are needed which are better suited to the requirements of both a minimally-trained knowledge base user and a skilled AI researcher.
In order to understand the context of the present invention, it is helpful to study the background developments in AI technology as they relate to the present invention. A primary source of information is The Handbook of Artificial Intelligence, Volume I, edited by Avron Barr and Edward Feigenbaum (published by William A. Kaufmann, Inc., of Los Altos, Cal.), Chapter III, "Knowledge Representation". The subject matter of this chapter is incorporated herein by reference and made a part hereof.
It is helpful to understand what is meant by knowledge and a knowledge base as now understood. Knowledge in the pragmatic terms of artificial intelligence is described in terms of its representation. Knowledge is a combination of data structures and interpretive procedures which, if suitably manipulated (as by a suitably programmed computing machine), will lead to what might best be termed "knowledgeable" behavior. A knowledge base is a set of knowledge representations which describes a domain of knowledge. A knowledge base is to an artificial intelligence environment what a database is to a conventional computer program. Unlike a database, however, a computer knowledge base can include executable program material within a defined record herein called a slot.
Knowledge representation techniques and theories are still in evolution. Nevertheless, knowledge representation appears to be classifiable into three categories.
The first category is that of descriptive knowledge. This category is the collection and classification of facts and categorizations about an idea or entity which might be acted upon. The basic units of descriptive knowledge are generally called frames, as hereinafter explained. They have also been known variously as units, concepts or objects. The term frame lacks some precision of meaning due to its use in other disciplines. Therefore, hereinafter a basic unit of descriptive knowledge is denoted a knowledge representation frame or KR frame. A KR frame contains one or more slots. However, any hierarchical data structure can be described in terms of nodes of information containing slots as components of the node. The descriptions herein therefore are not necessarily limited to KR frame applications, but may find application in any similarly organized hierarchical data structure.
The second category of knowledge representation is that of procedural representation in the form of rules or structured reasoning procedures. This category includes the structural capability to make choices. The premise-conclusion (IF THEN) format is a typical representation of a procedural knowledge conditional expression. Procedural knowledge emphasizes action and is encoded into a knowledge base as a rule in conditional expression form. The procedural knowledge may reside in a slot of a KR frame.
The third category is that of logic programming. Knowledge is represented as first order predicate calculus statements. Examples of languages using logic programming are the language of the so-called fifth generation computers of the Japanese, called PROLOG and the language MRS employed at Stanford University.
Over approximately the past decade, various attempts have been made to develop commercially useful knowledge representation languages which are useful for research and eventually for commercial applications. Among the efforts have been FRL (Frame Representation Language), KRL (Knowledge Representation Language), KL-ONE, NIKL, SMALLTALK, STROBE and UNITS. The present invention is the direct result of analyzing and then totally reworking the UNITS language coupled with discovery of solutions to problems to permit the practical manipulation of descriptive knowledge representation and procedural knowledge representation in the same environment. The result is a higher-level flexible knowledge representation "language" which has been identified as the KEE "language". Moreover, the KEE "language" has the elements of a knowledge base itself, which adds versatility heretofore unknown among artificial intelligence development tools.
One of the attributes of artificial intelligence is the concept of inheritance. It is a development of the idea of using a hierarchical structure for relating a knowledge base or database. The key to these structures is the concept of connecting relations between structures of data or knowledge through which information about attributes may pass to other structures of data or knowledge. The concept of inheritance has a number of advantages. First, an inheritance mechanism allows the specification of many components of a data structure or knowledge structure through reference to other data structures or knowledge structures. As used herein, high-level data structures or knowledge structures refer to organized collections of simpler data structures or knowledge structures, such as a collection of various relations in a relational database sense, or a collection of logical assertions as in the predicate calculus sense. Second, an inheritance mechanism can assure consistency among high-level data or knowledge structures. That is, the inheritance mechanism can be used to specify that a given data or knowledge structure must obey restrictions placed on characteristics from other data or knowledge structures. inherited from other data or knowledge structures.
Third, the inheritance mechanism allows the implementation of semantics. That is, the inheritance mechanism is a technique for combining higher level concepts and specifying meaning.
The concept of representing knowledge as hierarchical data structures with inheritance was first referred to in terms of "frames" by its most prominent early supporter, Marvin Minsky of the Massachusetts Institute of Technology. Minsky gave the first general description of the concept and laid the intellectual groundwork for development of practical systems implementation of a frame-based system. Subsequent work in first generation knowledge representation systems produced very stylized inheritance mechanisms lacking in flexibility or yielding inheritance structures which were cumbersome and so slow as to be of only limited utility in large knowledge bases.
There are two general strategies for when to perform inheritance, namely, "inherit on store" and "inherit on fetch". Inherit on store causes inheritance to be performed only when a value is stored in a slot. Inherit on fetch causes inheritance to be performed only when a value is retrieved from a slot. Nearly all prior languages have employed inherit on fetch schemes because of the assumption that inheritance was such an inefficient process that inheritance was best delayed until it became necessary to use values actually requiring inheritance. Inherit on fetch was therefore the preferred inheritance strategy.
Inherit on store was considered inherently cumbersome because it required the performance of inheritance on every descendant, some of whose values may not be of interest, thus requiring unnecessary work and loss of time. However, the inherit on fetch strategy requires more complex bookkeeping, making the inherit on fetch strategy relatively costly in a typical application. The lowest element in each tree is most likely to be changed most often. An inherit on fetch strategy more frequently results in developing a subgraph stretching from a bottom node through top nodes. Such a mechanism can be extremely time consuming and thus very costly.
Previous inheritance technology has generally recognized two kinds of values elements in a slot. The values recognized have been the local value, or the value given locally by the slot definition, and the inherited value, or the value expressed by the slot of the local KR frame. Conventional technology has taught that inheritance of attributes could only be correctly implemented and expressed by collecting local information and collecting all local information of all ancestral slots each time KR frame or data structure relations changed. Heretofore, conventional inheritance processes operated by performing a lookup of potentially all ancestor nodes in order to determine inherited information, and then such information was combined with local information to yield an "inherited value". A full lookup or traversal could only be avoided in cases where there was special information about how the inheritance was to be performed along the paths of the inheritance structure. The known techniques for avoiding a complete reconstruction of the inheritance structure have required that each kind of inheritance mechanism encode its own particular way of bypassing or shortcutting the traversal task. What is needed is a mechanism for improving or eliminating the known cumbersome inheritance techniques.